//给出整数n,求构造出来的搜索二叉树有多少种
//首先n=1,1.
//n=2,2 以1为节点和以2为节点
//确定dp[i]为i个节点构造出来的搜索二叉树有多少种
//取n，当到i时以i为根节点，前面有i-1个，后面又有n-i个，那么共有dp[i-1]*dp[n-i]种组合
//那么从就可以知道dp[i]=dp[0]dp[n-1]+dp[1]dp[n-2]......+dp[n-2]dp[1]dp[n-1]dp[0]
//所以要初始化dp[0]=1
#include <vector>
using std::vector;
int numTrees(int n) {
    vector<int> dp(n+1);
    dp[0]=1;
    dp[1]=1;
    for(int i=2;i<=n;i++){
        for(int j=0;j<=i-1;j++)
            dp[i]+=dp[j]*dp[i-j-1];
    }
    return dp[n];
}